package algorithm.double_pointer;


/**
 * 双指针
 * 1. 快慢指针
 * 主要解决：链表中的问题， 比如典型的判定链表中是否包含环；
 * 2. 左右指针
 */
public class Template {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }

    // 1. 判定链表中是否有环

    /**
     * 快慢指针：链表中是否有环
     */
    boolean hasCycle(ListNode head) {
        while (head != null) {
            head = head.next;
        }
        return false;
    }

    /**
     * 是否存在环，如果存在环，两者必然相遇
     *
     * @param head 链表头节点
     * @return 返回boolean值
     */
    boolean hasCycle1(ListNode head) {
        ListNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            // fast快指针每次前进两步
            fast = fast.next.next;
            // slow慢指针每次前进一步；
            slow = slow.next;
            // 如果存在环，快慢指针必然相遇
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    // 2. 已知链表中有环，返回这个环的起始位置
    ListNode detectCycle(ListNode head) {
        ListNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        // 上面的代码类似hasCycle函数
        // 先把一个指针重新指向head
        slow = head;
        while (slow != fast) {
            // 两个指针以相同的速度前进
            fast = fast.next;
            slow = slow.next;
        }
        // 两个指针相遇的那个单链表节点就是环的起点
        return slow;
    }

    // 左右指针
    // 左右指针一般运用在数组问题中，实际是指两个索引值，一般初始化为left=0; right=len(nums)-1;

    // 简单的二分搜索
    int binarySearch(int[] nums, int target) {
        // 左右指针在数组的两端初始化
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (right + left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        return -1;
    }

    // 两数之和：输入一个已知按照升序排列的有序数组nums和一个目标值target，在nums中找到两个数使得它们想加之和等于target，返回这两个数的索引
    // 注意：只要数组有序，就应该想到双指针技巧
    int[] twoSum(int[] nums, int target) {
        // 左右指针在数组的两端初始化
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                left++; // 让sum大一点
            } else {
                right--; // 让sum小一点
            }
        }
        return new int[]{-1, -1};
    }

    // 反转数组
    void reverse(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            // 交换nums[left]和nums[right]的位置
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }

    // 344. 反转字符串
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while (left < right) {
            // 交换位置
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }

    // 541. 反转字符串 II
    public String reverseStr(String s, int k) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        for (int i = 0; i < n; i += 2 * k) {
            int start = i;
            // 这里的i+k-1是已知每一轮要对长度为k的区间进行反转
            // 当索引i开始时，这个区间的末尾位置自然是i+k-1。这是因为索引是从0开始计数的，长度为k的区间，其最后一个元素的索引就是起始索引加上k-1
            int end = Math.min(i + k - 1, n - 1);
            while (start < end) {
                char temp = chars[start];
                chars[start] = chars[end];
                chars[end] = temp;
                start++;
                end--;
            }
        }
        return new String(chars);
    }
}
